#define ElemType int
#include <cstdlib>

struct LinkNode //链队列结点(单链表结点)
{
    ElemType data;
    struct LinkNode *next;
};

struct LinkQueue //链式队列(链队列)
{
    LinkNode *front, *rear; //队列的队头和队尾指针
};



//这里以带头结点 且 队头指针指向队头元素，队尾指针指向队尾元素的链式队列为例！

void InitQueue(LinkQueue &Q) //初始化
{
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点，且队头和队尾指针指向同一块区域
    Q.front->next = NULL;                                    //初始为空
}

bool IsEmpty(LinkQueue Q) //判队空
{
    if (Q.front == Q.rear) //队空条件
        return true;
    else
        return false;
}

void EnQueue(LinkQueue &Q, ElemType x) //入队
{
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //创建新结点
    
    //插入到队尾
    s->data = x; s->next = NULL;                        
    Q.rear->next = s;

    Q.rear = s; //队尾指针指向新的队尾
}

bool DeQueue(LinkQueue &Q, ElemType &x) //出队
{
    if (Q.front == Q.rear)       //队空则报错
        return false;
    LinkNode *p = Q.front->next; //新建一个指针指向队首
    x = p->data;                 //把队首元素通过x带回来
    Q.front->next = p->next;     //删除队首元素
    if (Q.rear == p)             //若原队列中只有一个结点，删除后变空(即删除后只剩下一个头结点)
        Q.rear = Q.front;
    free(p);                     //释放p
    return true;
}